//#define _CRT_SECURE_NO_WARNINGS 1
//#include<iostream>
//
//#include<unordered_map>
//using namespace std;
//
//
//
//class LRUCache
//{
//private:
//    unordered_map<int, list<pair<int, int>>::iterator> h;
//    list<pair<int, int>> list_;
//    int capacity_;
//public:
//    LRUCache(int capacity) :list_(capacity), capacity_(capacity)
//    {
//
//    }
//
//    int get(int key)
//    {
//        if (!h.count(key))
//        {
//            return -1;
//        }
//        else
//        {
//            list<pair<int, int>>::iterator it = h[key];
//            int ret = it->second;
//
//            list_.erase(it);
//            list_.push_front({ key,ret });
//            h[key] = list_.begin();
//            return ret;
//        }
//    }
//
//    void put(int key, int value)
//    {
//        if (!h.count(key))
//        {
//            if (list_.size() == capacity_)
//            {
//                list<pair<int, int>>::iterator it = --list_.end();
//                h.erase(it->first);
//                list_.pop_back();
//
//            }
//            list_.push_front({ key,value });
//            h[key] = list_.begin();
//        }
//        else
//        {
//            list<pair<int, int>>::iterator it = h[key];
//            list_.erase(it);
//            list_.push_front({ key,value });
//            h[key] = list_.begin();
//
//        }
//    }
//};
//
///**
// * Your LRUCache object will be instantiated and called as such:
// * LRUCache* obj = new LRUCache(capacity);
// * int param_1 = obj->get(key);
// * obj->put(key,value);
// */